home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / edit / tde40.zip / regx.c < prev    next >
C/C++ Source or Header  |  1994-06-05  |  38KB  |  1,302 lines
  1. /*
  2.  * These functions compile a regular expression into an NFA and recognize
  3.  * a pattern.
  4.  *
  5.  * Regular expressions are often used to describe a pattern that might
  6.  * match several different or similar words.  An example of a regular
  7.  * expression subset is the wild card characters '*' and '?' used to list
  8.  * files in a directory.
  9.  *
  10.  * Might as well read the books and papers written by those who first wrote
  11.  * the various [a-z]?greps.  Ken Thompson was the author of grep.  In one
  12.  * weekend, Al Aho wrote egrep and fgrep.  Incidentally, when Dr. Aho was
  13.  * the guest speaker at the Distinguished Lecture Series at Georgia Tech,
  14.  * he personally autographed my copy of his book  _Compilers:  Principles,
  15.  * Techniques, and Tools_, aka the "Dragon Book."
  16.  *
  17.  * See:
  18.  *
  19.  *   Ken Thompson, "Regular Expression Search Algorithm."  _Communications
  20.  *      of the ACM_, 11 (No. 6): 419-422, 1968.
  21.  *
  22.  *   Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, _Compilers: Principles,
  23.  *      Techniques, and Tools_, Addison-Wesley, Reading, Mass., 1986,
  24.  *      Chapter 3, "Lexical Analysis", pp 83-158.  ISBN 0-201-10088-6.
  25.  *
  26.  *   Robert Sedgewick, _Algorithms in C_, Addison-Wesley, Reading, Mass.,
  27.  *      1990, Chapter 20, "Pattern Matching", pp. 293-303, and Chapter 21,
  28.  *      "Parsing", pp. 305-317.  ISBN 0-201-51425-7.
  29.  *
  30.  *   Andrew Hume, "A Tale of Two Greps."  _Software--Practice and Experience_,
  31.  *      18 (No. 11): 1063-1072, 1988.
  32.  *
  33.  *
  34.  *                         Regular Expressions in TDE
  35.  *
  36.  * The core of the regular expression search algorithm in TDE is based on
  37.  * the nondeterministic finite-state machine in Dr. Segdewick's book.
  38.  * Additional parsing, operator precedence, and nfa construction and
  39.  * simulation info is from Dr. Aho's book.  The nfa node naming convention
  40.  * and additional nfa construction guidelines are from Ken Thompson's paper.
  41.  * I'm much too stupid to compile a regular expression into assembly language
  42.  * as suggested in Ken Thompson's paper, but I did get the idea to do the
  43.  * next best thing and added C library functions as NNODE terminal types.
  44.  *
  45.  * The local global NFA is builded with two arrays and a deque.  The
  46.  * first array, next1, in the NFA is used to hold the path for lambda
  47.  * transitions.  The second array, next2, is used to hold alternate paths.
  48.  * Next1 can hold all types of nodes, but it gets priority for lambda
  49.  * transitions.  The deque is a circular array where future states are queued
  50.  * in the head and present states are pushed in the tail.
  51.  *
  52.  * Searching for regular expressions in TDE is not very fast.  The worst
  53.  * case search, .*x, where x is any word or letter, is probably the slowest
  54.  * of any implementation with a regular expression search function.  However,
  55.  * TDE can handle a large regular expression subset.
  56.  *
  57.  * In version 3.1, I added BOW and EOW (beginning of word and end of word.)
  58.  *
  59.  * In version 3.2, the macro letters were moved to letters.h per Byrial Jensen.
  60.  * We also use the bj_isxxx( ) functions to test whether a letter falls into
  61.  * a predefined macro class.
  62.  *
  63.  * New editor name:  TDE, the Thomson-Davis Editor.
  64.  * Author:           Frank Davis
  65.  * Date:             June 5, 1991, version 1.0
  66.  * Date:             July 29, 1991, version 1.1
  67.  * Date:             October 5, 1991, version 1.2
  68.  * Date:             January 20, 1992, version 1.3
  69.  * Date:             February 17, 1992, version 1.4
  70.  * Date:             April 1, 1992, version 1.5
  71.  * Date:             June 5, 1992, version 2.0
  72.  * Date:             October 31, 1992, version 2.1
  73.  * Date:             April 1, 1993, version 2.2
  74.  * Date:             June 5, 1993, version 3.0
  75.  * Date:             August 29, 1993, version 3.1
  76.  * Date:             November 13, 1993, version 3.2
  77.  * Date:             June 5, 1994, version 4.0
  78.  *
  79.  * This code is released into the public domain, Frank Davis.
  80.  * You may use and distribute it freely.
  81.  */
  82.  
  83. #include "tdestr.h"
  84. #include "common.h"
  85. #include "tdefunc.h"
  86. #include "define.h"
  87.  
  88. #ifndef min
  89.  #define min(a,b)       (((a) < (b)) ? (a) : (b))
  90. #endif
  91.  
  92. /*
  93.  * types of nodes in the NFA.
  94.  *
  95.  * let's use the node naming convention in Ken Thompson's reg ex paper.
  96.  */
  97. #define CNODE           0
  98. #define NNODE           1
  99.  
  100. #define SCAN            -1
  101.  
  102. /*
  103.  * types of terminals in NNODEs.
  104.  *
  105.  * starting with simple ASCII terminals, it's easy to build in other types of
  106.  *  terminals, e.g. wild chars, BOL, EOL, and character classes.  actually,
  107.  *  we can easily build ANSI C ctype library function NNODEs.
  108.  */
  109. #define STRAIGHT_ASCII  0
  110. #define IGNORE_ASCII    1
  111. #define WILD            2
  112. #define BOL             3
  113. #define EOL             4
  114. #define CLASS           5
  115. #define NOTCLASS        6
  116. #define WHITESPACE      7
  117. #define ALPHA           8
  118. #define UPPER           9
  119. #define LOWER           10
  120. #define ALPHANUM        11
  121. #define DECIMAL         12
  122. #define HEX             13
  123. #define BOW             14
  124. #define EOW             15
  125.  
  126.  
  127. /*
  128.  * types of terminals in CNODEs.
  129.  */
  130. #define START           0
  131. #define ACCEPT          1
  132. #define OR_NODE         2
  133. #define JUXTA           3
  134. #define CLOSURE         4
  135. #define ZERO_OR_ONE     5
  136.  
  137.  
  138. int  lookahead;
  139. int  regx_rc;
  140. int  reg_len;
  141. int  parser_state;
  142. char class_bits[32];
  143. int  bit[8] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
  144. int  c1;
  145. int  c2;
  146. int  ttype;
  147. int  regx_error_line;
  148.  
  149. NFA_TYPE  *nfa_pointer;
  150.  
  151. int  nfa_status;
  152. int  search_len;
  153. int  search_col;
  154. text_ptr search_string;
  155.  
  156. int  queued_states[REGX_SIZE+2];
  157. int  deque[REGX_SIZE*2];
  158. int  dq_head;
  159. int  dq_tail;
  160. int  stacked_node_count;
  161. int  reset_count;
  162.  
  163.  
  164. /*
  165.  * Name:    find_regx
  166.  * Purpose: To set up and find a regular expression.
  167.  * Date:    June 5, 1993
  168.  * Passed:  window:  pointer to current window
  169.  * Notes:   Keep the regular expression until changed.
  170.  */
  171. int  find_regx( TDE_WIN *window )
  172. {
  173. int  direction;
  174. int  new_string;
  175. long found_line;
  176. long bin_offset;
  177. line_list_ptr ll;
  178. register TDE_WIN *win;  /* put window pointer in a register */
  179. int  rc;
  180. int  old_rcol;
  181. int  rcol;
  182. char answer[MAX_COLS+2];
  183. char temp[MAX_COLS+2];
  184.  
  185.    switch (g_status.command) {
  186.       case FindRegX :
  187.          new_string = TRUE;
  188.          direction  = FORWARD;
  189.          break;
  190.       case RepeatFindRegX :
  191.          new_string =  regx.search_defined != OK ? TRUE : FALSE;
  192.          direction  = FORWARD;
  193.          break;
  194.       case RepeatFindRegXBackward :
  195.          new_string =  regx.search_defined != OK ? TRUE : FALSE;
  196.          direction  = BACKWARD;
  197.          break;
  198.       default :
  199.          new_string = 0;
  200.          direction  = 0;
  201.          assert( FALSE );
  202.          break;
  203.    }
  204.  
  205.    win = window;
  206.    entab_linebuff( );
  207.    if (un_copy_line( win->ll, win, TRUE ) == ERROR)
  208.       return( ERROR );
  209.  
  210.    regx_error_line = win->bottom_line;
  211.  
  212.    /*
  213.     * get search text, using previous as default
  214.     */
  215.    rc = OK;
  216.    if (new_string == TRUE) {
  217.       *answer = '\0';
  218.       if (regx.search_defined == OK) {
  219.  
  220.          assert( strlen( (char *)regx.pattern ) < (size_t)g_display.ncols );
  221.  
  222.          strcpy( answer, (char *)regx.pattern );
  223.       }
  224.  
  225.       /*
  226.        * string to find:
  227.        */
  228.       if (get_name( reg1, win->bottom_line, answer,
  229.                  g_display.message_color ) != OK  ||  *answer == '\0')
  230.          return( ERROR );
  231.       regx.search_defined = OK;
  232.  
  233.       assert( strlen( answer ) < (size_t)g_display.ncols );
  234.  
  235.       strcpy( (char *)regx.pattern, answer );
  236.       rc = build_nfa( );
  237.       if (rc == ERROR)
  238.          regx.search_defined = ERROR;
  239.    }
  240.  
  241.    if (regx.search_defined == OK) {
  242.       old_rcol = win->rcol;
  243.       if (mode.inflate_tabs)
  244.          win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol);
  245.       update_line( win );
  246.       show_search_message( SEARCHING, g_display.diag_color );
  247.       bin_offset = win->bin_offset;
  248.       if (direction == FORWARD) {
  249.          if ((ll = forward_regx_search( win, &found_line, &rcol )) != NULL) {
  250.             if (g_status.wrapped && g_status.macro_executing)
  251.